package tree.leetcode_98_medium;

public class DFS {
    public boolean isValidBST(TreeNode root){
        if(root == null){
            return true;
        }
        return isBST(root,Long.MAX_VALUE,Long.MIN_VALUE);
    }

    /**
     * 递归判断是否是二叉搜索树：
     * 左子树是二叉搜索树、右子树是二叉搜索树、左子树的值都小于根节点的值、右子树的值都大于根节点的值
     * @param root  根节点
     * @param maxValue 下界，判断右子树时，根节点就是下界，所有左子树的节点值都不能大于下界
     * @param minValue 上界，判断左子树时，根节点就是上界，所有左子树的节点值都不能大于上界
     * @return      返回结果
     */
    public boolean isBST(TreeNode root, long maxValue, long minValue){
        int res = root.val;
        if(res > maxValue || res < minValue){
            return false;
        }
        if(!isBST(root.left,res,minValue)){
            return false;
        }
        if(!isBST(root.right,maxValue,res)){
            return false;
        }
        return true;
    }
}
